【STL】deque容器详解（deque常用的操作函数、构造函数、赋值操作、大小操作、插入和删除、数据存取） |
您所在的位置：网站首页 › deque 原理 › 【STL】deque容器详解（deque常用的操作函数、构造函数、赋值操作、大小操作、插入和删除、数据存取） |
【STL】deque容器详解（deque常用的操作函数、构造函数、赋值操作、大小操作、插入和删除、数据存取）
|
目录
1. deque容器 简介2. deque常用的操作函数3. 构造函数4. 赋值操作5. 大小操作6. 插入和删除7. 数据存取8. 排序
1. deque容器 简介
（1）功能：双端数组，可以对头端进行插入删除操作，也可以对尾端进行插入和删除操作。 （2） deque与vector区别： vector对于头部的插入效率低，数据量越大，效率越低，例如头部后有十万个数据，则往头部插入一个数据时，十万个数据都需要往后挪一挪才能在头部插入数据。deque相对而言，对头部的插入删除速度会比vector快。vector访问元素时的速度会比deque快，这和两者内部实现有关。 （3）deque内部工作原理： 和 vector 容器采用连续的线性空间不同，deque 容器存储数据的空间是由一段一段等长的连续空间构成，各段空间之间并不一定是连续的，可以位于在内存的不同区域。 为了管理这些连续空间，deque 容器用数组存储着各个连续空间的首地址。也就是说，数组中存储的都是指针，指向那些真正用来存储数据的各个连续空间。
通过建立数组，deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果。换句话说，当 deque 容器需要在头部或尾部增加存储空间时，它会申请一段新的连续空间，同时在数组的开头或结尾添加指向该空间的指针，由此该空间就串接到了 deque 容器的头部或尾部。 deque 容器的分段存储结构，提高了在序列两端添加或删除元素的效率，但也使该容器迭代器的底层实现变得更复杂。 （4）deque容器迭代器的底层实现 由于 deque 容器底层将序列中的元素分别存储到了不同段的连续空间中，因此要想实现迭代器的功能，必须先解决如下 2 个问题： ①迭代器在遍历 deque 容器时，必须能够确认各个连续空间在数组中的位置； ②迭代器在遍历某个具体的连续空间时，必须能够判断自己是否已经处于空间的边缘位置。如果是，则一旦前进或者后退，就需要跳跃到上一个或者下一个连续空间中。 实现：迭代器内部包含 4 个指针，它们各自的作用为： cur：指向当前正在遍历的元素； first：指向当前连续空间的首地址； last：指向当前连续空间的末尾地址； node：它是一个二级指针，用于指向数组中存储的指向当前连续空间的指针。 2. deque常用的操作函数 1. deque deq; //默认构造形式 2. deque d2(d1.begin(),d1.end()); //将d1中[begin,end)区间中的元素拷贝给本身。 3. deque(n,elem); //构造函数将n个elem拷贝给本身 4. deque(const deque &deq); //拷贝构造函数 5. deque& operator=(const deque &deq); //重载等号操作符 6. assign(beg, end); //将[beg,end)区间中的数据拷贝赋值给本身。 7. assign(n,elem); //将n个elem拷贝赋值给本身。 8. empty(); //判断容器是否为空 9. size(); //返回容器中的元素的个数 10. resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。 //如果容器变短，则末尾超出容器长度的元素被删除。 11. resize(num,elem); //重新指定容器的长度为num，若容器变成，则以elem值填充新位置。 //如果容器变短，则末尾超出容器长度的元素被删除。 12. push_back(elem); //在容器尾部添加一个数据 13. push_front(elem); //在容器头部插入一个数据 14. pop_back(); //删除容器最后一个数据 15. pop_front(); //删除容器第一个数据 16. insert(pos,elem); //在pos位置插入一个elem元素的拷贝，返回新数据的位置。 17. insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值 18. insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据，无返回值 19. clear(); //清空容器的所有数据 20. erase(beg,end); //删除[beg,end)区间的数据，返回下一个数据的位置。 21. erase(pos); //删除pos位置的数据，返回下一个数据的位置。 22. at(int idx); //返回索引idx所指的数据 23. operator[]; //返回索引idx所指的数据 24. front(); //返回容器中第一个数据元素 25. back(); //返回容器中最后一个数据元素 3. 构造函数（1）功能描述：deque容器构造。 （2）函数原型： 1. deque deq; //默认构造形式 2. deque d2(d1.begin(),d1.end()); //将d1中[begin,end)区间中的元素拷贝给本身。 3. deque(n,elem); //构造函数将n个elem拷贝给本身 4. deque(const deque &deq); //拷贝构造函数（3）deque容器和vector容器的构造方式几乎一致，灵活使用即可。 #include #include using namespace std; //deque容器 构造函数 void printDeuque(const deque& d) //const 防止进行写操作，只能进行读 { for (deque::const_iterator it = d.begin(); it != d.end(); it++) //表示只读迭代器 { //*it = 100; const使得当进行写操作时，会报错，会提示，避免了进行修改操作 cout d1.push_back(i); } printDeuque(d1); //区间的方式构造 deque d2(d1.begin(),d1.end()); printDeuque(d2); //n个值的方式构造 deque d3(10,100); printDeuque(d3); //拷贝构造 deque d4(d3); printDeuque(d4); } int main() { test01(); return 0; }运行结果： （1）功能描述：给deque容器进行赋值。 （2） 函数原型： 1. deque& operator=(const deque &deq); //重载等号操作符 2. assign(beg, end); //将[beg,end)区间中的数据拷贝赋值给本身。 3. assign(n,elem); //将n个elem拷贝赋值给本身。（3）deque赋值操作与vector相同。 #include #include using namespace std; //deque容器 赋值操作 void printDeuque(const deque& d) { for (deque::const_iterator it = d.begin(); it != d.end(); it++) //表示只读迭代器 { cout d1.push_back(i); } printDeuque(d1); //operator= 赋值 deque d2; d2 = d1; printDeuque(d2); //assign 赋值 deque d3; d3.assign(d1.begin(), d1.end()); printDeuque(d3); deque d4(10,100); printDeuque(d4); } int main() { test02(); return 0; }运行结果： （1）功能描述：对deque容器的大小进行操作。 （2）函数原型： 1. deque.empty(); //判断容器是否为空 2. deque.size(); //返回容器中的元素的个数 3. deque.resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。 //如果容器变短，则末尾超出容器长度的元素被删除。 4. deque.resize(num,elem); //重新指定容器的长度为num，若容器变成，则以elem值填充新位置。 //如果容器变短，则末尾超出容器长度的元素被删除。 #include #include using namespace std; //deque容器 大小操作 void printDeuque(const deque& d) { for (deque::const_iterator it = d.begin(); it != d.end(); it++) //表示只读迭代器 { cout d1.push_back(i); } printDeuque(d1); if (d1.empty()) { cout test03(); return 0; }运行结果为： （1）功能描述：向deque容器中插入和删除数据。 （2）函数原型： 1. push_back(elem); //在容器尾部添加一个数据 2. push_front(elem); //在容器头部插入一个数据 3. pop_back(); //删除容器最后一个数据 4. pop_front(); //删除容器第一个数据 5. insert(pos,elem); //在pos位置插入一个elem元素的拷贝，返回新数据的位置。 6. insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值 7. insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据，无返回值 8. clear(); //清空容器的所有数据 9. erase(beg,end); //删除[beg,end)区间的数据，返回下一个数据的位置。 10. erase(pos); //删除pos位置的数据，返回下一个数据的位置。 #include #include using namespace std; //deque容器 插入和删除 void printDeuque(const deque& d) { for (deque::const_iterator it = d.begin(); it != d.end(); it++) //表示只读迭代器 { cout deque d2; d2.push_back(10); d2.push_back(20); d2.push_front(100); d2.push_front(200); printDeuque(d2); d2.insert(d2.begin(), 1000); printDeuque(d2); d2.insert(d2.begin(), 2, 9999); printDeuque(d2); deque d3; d3.push_back(1); d3.push_back(2); d3.push_front(3); d3.insert(d3.begin(), d2.begin(), d2.end()); //在d3.begin()的位置，插入区间d2.begin()-d2.end()之间的数 printDeuque(d3); } void test06() { deque d1; d1.push_back(10); d1.push_back(20); d1.push_front(100); d1.push_front(200); //删除 deque::iterator it = d1.begin(); it++; d1.erase(it); //d1.erase()为删除所有;d1.clear()也为清空容器所有数据 printDeuque(d1); //按区间方式删除 d1.erase(d1.begin(), d1.end()); printDeuque(d1); } int main() { test04(); test05(); test06(); return 0; }运行结果为： （1）功能描述：对deque中的数据的存取操作。 （2）函数原型： 1. at(int idx); //返回索引idx所指的数据 2. operator[]; //返回索引idx所指的数据 3. front(); //返回容器中第一个数据元素 4. back(); //返回容器中最后一个数据元素（3）除了用迭代器获取deque容器中元素，[]和at也可以。 #include #include using namespace std; //deque容器 数据存取 void printDeuque(const deque&d) { for (deque::const_iterator it = d.begin(); it != d.end(); it++) //表示只读迭代器 { cout cout test07(); return 0; }运行结果为： （1）利用算法实现对deque容器进行排序。 （2） 算法： 1. sort(iterator beg, iterator end) //对beg和end区间内元素进行排序（3）sort算法非常实用，使用时包含头文件algorithm即可。 #include #include #include //标准算法头文件 using namespace std; //deque容器 排序操作 void printDeuque(const deque&d) { for (deque::const_iterator it = d.begin(); it != d.end(); it++) //表示只读迭代器 { cout test08(); return 0; }运行结果为： |
【本文地址】